#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

#ifndef DATATYPE
#define DATATYPE Datatype
#endif

#define Datatype int

typedef struct node
{
    Datatype data;
    struct node *next;
}list_node_t;

typedef struct queue
{
    list_node_t *front;
    list_node_t *rear;
}queue_chained;


typedef struct stack
{
    Datatype *p_base;
    int num;
    int top;
}stack_t;

stack_t *init_stack(int n)
{
    stack_t *p_stack = calloc(1, sizeof(stack_t));
    if(p_stack == NULL)
    {
        perror("calloc stack failed");
    }

    p_stack->p_base = calloc(n, sizeof(Datatype));

    p_stack->num = n;
    p_stack->top = -1;
    return p_stack;
}

bool empty_stack(stack_t *p_stack)
{
    return p_stack->top == -1;
}

bool full_stack(stack_t *p_stack)
{
    return p_stack->top == p_stack->num - 1;
}

void push_stack(stack_t *p_stack, Datatype data)
{
    p_stack->top++;
    p_stack->p_base[p_stack->top] = data;
    // printf("[push_stack]:p_stack->p_base[%d]=%d\n", p_stack->top, p_stack->p_base[p_stack->top]);
}   

Datatype pull_stack(stack_t *p_stack)
{
    p_stack->top--;
    // printf("[pull_stack]:p_stack->p_base[%d]=%d\n", p_stack->top+1, p_stack->p_base[p_stack->top+1]);
    return p_stack->p_base[p_stack->top+1];
}

Datatype pop(stack_t *p_stack)
{
    return p_stack->p_base[p_stack->top];
}




queue_chained *init_queue(void)
{
    queue_chained *s = calloc(1, sizeof(queue_chained));
    if(s == NULL)
    {
        perror("calloc chained queue failed");
        return NULL;
    }
    s->front = NULL;
    s->rear = NULL;
    return s;
}

list_node_t *new_list_node(Datatype value)
{
    list_node_t *new_node = calloc(1, sizeof(list_node_t));
    if(new_list_node == NULL)
    {
        perror("calloc new_node failed");
        return NULL;
    }
    new_node->data = value;
    new_node->next = NULL;
    return new_node;
}

bool empty_queue(queue_chained *p_queue)
{
    return p_queue->front == NULL;
}

void enqueue(queue_chained *p_queue, list_node_t *p_node)
{
    if(empty_queue(p_queue))     //空队列
    {
        p_queue->front = p_node;
        p_queue->rear = p_node;
    }
    else
    {
        p_queue->rear->next = p_node;     //需要先将队列终端的元素（链表节点）串联起来
        p_queue->rear = p_node;                 //队列尾巴指向该节点
    }
}

Datatype dequeue(queue_chained *p_queue)
{
    list_node_t *tmp = NULL;
    Datatype value = 0;

    if(empty_queue(p_queue))
    {
        printf("err: queue is empty, we can not dequeue!\n");
        return -1;
    }
    tmp = p_queue->front;
    value = tmp->data;
    p_queue->front = tmp->next;
    free(tmp);
    if(empty_queue(p_queue))                //如果出队以后队列空了，记得队尾也要指向空
    {
        p_queue->rear = NULL;
    }
    return value;
}

int get_queue_len(queue_chained *p_queue)
{
    int len = 0;
    list_node_t *tmp = p_queue->front;
    
    while(tmp != NULL)
    {
        len++;
        tmp = tmp->next;
    }
    return len;
}

void print_queue(queue_chained *p_queue)
{
    list_node_t *tmp = p_queue->front;
    
    while(tmp != NULL)
    {
        printf("%d->", tmp->data);
        tmp = tmp->next;
    }
    printf("\n");
}

void destory_queue(queue_chained *p_queue)
{
    list_node_t *tmp = p_queue->front;
    list_node_t *death = tmp;
    while (death != NULL)
    {
        tmp = tmp->next;
        free(death);
        death = tmp;
    }
    p_queue->front = NULL;
    p_queue->rear = NULL;
    free(p_queue);
}

void pull_stack_over_enqueue(stack_t *p_stack, queue_chained *p_queue)
{
    int ret = 0;
    list_node_t *new_node = NULL;
    if(!empty_stack(p_stack))
    {
        ret = pull_stack(p_stack);
        new_node = new_list_node(ret);
        enqueue(p_queue, new_node);
    }
}

bool check_ball_queue_status(queue_chained *p_queue)
{
    list_node_t *tmp = p_queue->front;
    while(tmp != NULL && tmp->next != NULL)
    {
        if(tmp->next->data > tmp->data)
        {
            tmp = tmp->next;
        }
        else
        {
            return false;
        }
    }
    return true;
}


int main(void)
{
    int i = 0;
    int ret = 0;
    list_node_t *new_node = NULL;

    queue_chained *queue_ball = init_queue();
    if(queue_ball == NULL)
        return -1;
    for(i=1; i<=27; i++)
    {
        new_node = new_list_node(i);
        enqueue(queue_ball, new_node);
    }

    stack_t *stack_min1 = init_stack(4);
    stack_t *stack_min5 = init_stack(11);
    stack_t *stack_min60 = init_stack(11);
    if(stack_min1 == NULL || stack_min5 == NULL || stack_min60 == NULL)
        return -1;

    while (1)
    {
        if(!empty_queue(queue_ball))        //如果球队列不空，先取一个球出来
        {
            ret = dequeue(queue_ball);
        }
        
        if(!full_stack(stack_min1))         //1min球栈没满，则入1min球栈
        {
            push_stack(stack_min1, ret);
        }
        else if(!full_stack(stack_min5))    //5min球栈没满，则入5min球栈，并把1min球栈全部入队列
        {
            push_stack(stack_min5, ret);
            pull_stack_over_enqueue(stack_min1, queue_ball);
        }
        else if(!full_stack(stack_min60))   //60min球栈没满，则入60min球栈，并把5min球栈全部入队列
        {
            push_stack(stack_min60, ret);
            pull_stack_over_enqueue(stack_min5, queue_ball);
        }
        else                                //三个栈全部满了
        {
            pull_stack_over_enqueue(stack_min1, queue_ball);
            pull_stack_over_enqueue(stack_min5, queue_ball);
            pull_stack_over_enqueue(stack_min60, queue_ball);
            new_node = new_list_node(ret);
            enqueue(queue_ball, new_node);
        }

        if(check_ball_queue_status(queue_ball))
        {
            printf("return back!!!\n");
            break;
        }
    }

    return 0;
}
